//package datastruct.list.impl;
//
//import datastruct.list.inter.IJoList;
//import datastruct.list.inter.IListConsumer;
//
//import java.lang.reflect.Array;
//import java.sql.Struct;
//import java.util.*;
//import java.util.concurrent.ConcurrentLinkedDeque;
//import java.util.concurrent.ConcurrentLinkedQueue;
//import java.util.concurrent.atomic.AtomicInteger;
//
//public class JoQuickList implements IJoList {
//
//    public static final int PAGE_SIZE = 4;
//    public static final int FORWARD = 0;
//    public static final int BACKWARD = 1;
//
//    public ConcurrentLinkedDeque<ArrayList<String>> data;
//    public AtomicInteger size;
//
//    private static class QLIterator {
//        public Iterator<ArrayList<String>> node;
//        public int offset;
//        public JoQuickList ql;
//        public int searchDirection = FORWARD;
//
//        public String get() {
//            ArrayList<String> page = page();
//            return page == null ? null : page.get(offset);
//        }
//
//        public void set(String val) {
//            ArrayList<String> page = page();
//            if (page != null) {
//                page.set(offset, val);
//            }
//        }
//
//        public ArrayList<String> page() {
//            ArrayList<String> page = null;
//            if (searchDirection == FORWARD && node.hasPrevious()) {
//                // 返回 page，同时向前移动一步
//                page =  node.previous();
//                // 调整回到原来的位置
//                node.next();
//            } else if (searchDirection == BACKWARD &&  node.hasNext()) {
//                // 返回 page，同时向后移动一步
//                page = node.next();
//                // 调整回到原来的位置
//                node.previous();
//            }
//            return page;
//        }
//
//        public boolean prev() {
//            if (offset > 0) {
//                offset--;
//                return true;
//            }
//            if (!node.hasPrevious()) {
//                return false;
//            }
//
//            ArrayList<String> page = node.previous();
//            offset = page.size()-1;
//            return true;
//        }
//
//        public boolean next() {
//            ArrayList<String> page = page();
//            if (offset < page.size()-1) {
//                offset++;
//                return true;
//            }
//
//            if (!node.hasNext()) {
//                return false;
//            }
//            offset = 0;
//            node.next();
//            return true;
//        }
//
////        public boolean atEnd() {
////            if (ql.size.intValue() == 0) {
////                return true;
////            }
////            if (node == ql.data.listIterator(ql.data.size()-1)) {
////                return true;
////            }
////
////            ArrayList<String> page = page();
////            return offset == page.size();
////        }
////
////        public boolean atBegin() {
////            if (ql.size.intValue() == 0) {
////                return true;
////            }
////            if (node != ql.data.listIterator(0)) {
////                return false;
////            }
////            return offset == 0;
////        }
//
//        public String remove() {
//            ArrayList<String> page = page();
//            String val = page.get(offset);
//            page.remove(val);
//            ql.size.getAndDecrement();
//            if (page.size() == 0) {
//                // 如果是最后一页，
//                if (!node.hasNext()) {
//                    node.previous();
//                    node.remove();
//                    offset = 0;
//                } else {
//                    node.next();
//                    node.remove();
//                    offset = 0;
//                }
//            }
//            return val;
//        }
//    }
//
//    public static JoQuickList makeQuicKList() {
//        JoQuickList list = new JoQuickList();
//        list.data = new ConcurrentLinkedDeque<>();
//        list.size = new AtomicInteger(0);
//        return list;
//    }
//
//    private synchronized QLIterator find(int index) {
//        if (index < 0 || index >= size.intValue()) {
//            return null;
//        }
//        int pageOffset = 0;
//
//
//        Iterator<ArrayList<String>> node = null;
//        ArrayList<String> page = null;
//        int pageBegin = 0, searchDirection = FORWARD;
//        if (index < size.intValue() / 2) {
//            node = data.iterator();
//            while (true) {
//                // 这里返回当前元素， 同时迭代器往后移动一步
//                page = node.next();
//                // 要找的元素，在这个 page 里
//                if (pageBegin + page.size() > index) {
//                    break;
//                }
//                pageBegin += page.size();
//            }
//        } else {
//            searchDirection = BACKWARD;
//            // 从后往前找
//            node = data.descendingIterator();
//            pageBegin = size.intValue();
//            while (true) {
//                page = node.next();
//                pageBegin -= page.size();
//                if (pageBegin <= index) {
//                    break;
//                }
//            }
//        }
//
//        pageOffset = index - pageBegin;
//        QLIterator iter = new QLIterator();
//        // 如果是从后往前找，那么 page = node.next
//        // 如果是从前往后找，那么 page = node.previous
//        iter.node = node;
//        iter.ql = this;
//        iter.offset = pageOffset;
//        iter.searchDirection = searchDirection;
//        return iter;
//    }
//
//    @Override
//    public void add(String val) {
//        size.getAndIncrement();
//        if (data.isEmpty()) {
//            ArrayList<String> page = new ArrayList<>();
//            page.add(val);
//            data.add(page);
//            return;
//        }
//
//        ArrayList<String> backNode = data.getLast();
//        if (backNode.size() == PAGE_SIZE) {
//            ArrayList<String> newPage = new ArrayList<>();
//            newPage.add(val);
//            data.add(newPage);
//            return;
//        }
//
//        backNode.add(val);
//    }
//
//
//    @Override
//    public String get(int index) {
//        QLIterator iter = find(index);
//        return iter == null ? null : iter.get();
//    }
//
//    @Override
//    public boolean set(int index, String val) {
//        QLIterator iter = find(index);
//        if (iter != null) {
//            iter.set(val);
//            return true;
//        }
//        return false;
//    }
//
//    @Override
//    public void insert(int index, String val, boolean isBefore) {
//        // 直接添加到尾部
//        if (index == size.intValue()) {
//            add(val);
//            return;
//        }
//
//        QLIterator iter = find(index);
//        if (iter == null) {
//            return;
//        }
//
//
//        ArrayList<String> page = iter.page();
//        if (page == null) {
//            return;
//        }
//
//        String oldVal = page.get(iter.offset);
//
//        // page 调用完后，node 已经往后
////        iter.node.previous();
//        if (page.size() < PAGE_SIZE) {
//            page.add(iter.offset, val);
//            size.getAndIncrement();
//            return;
//        }
//
//        data.
//
//        // 当前 page 已经满了，那么把这个 page 分成两半，
//        ArrayList<String> firstPart = new ArrayList<>(), secondPart = new ArrayList<>();
//
//
//        //  拷贝前半部分
//        for (int i = 0; i < PAGE_SIZE / 2; i++) {
//            String item = page.get(i);
//            if (item.equals(oldVal)) {
//                firstPart.add(val);
//            }
//            firstPart.add(item);
//        }
//
//
//        // 拷贝后半部分
//        for (int i=PAGE_SIZE/2;i<PAGE_SIZE;i++) {
//            String item = page.get(i);
//            if (item.equals(oldVal)) {
//                secondPart.add(val);
//            }
//            secondPart.add(item);
//        }
//
//        // 两个 page 重新加入
//        // 先用 firstPart 替换掉当前 page
//        iter.node.remove();
//        iter.node.set(firstPart);
//        // 然后把 secondPart 加到 firstPart 后面
////        if (iter.searchDirection == FORWARD) {
////            iter.node.next();
////        } else {
////            iter.node.previous();
////        }
//        // 这里 node.next 取的 page 有可能是 first part，这里先假设是，所以往后挪，后期再验证，如果不是，就挪回来
//        if (iter.node.hasNext()) {
//            ArrayList<String> nextPage = iter.node.next();
//            // 保证 second part 一定是排在 firstPart 后面
//            // 如果取的 page 不是 first part，就需要挪回去
//            if (nextPage != firstPart) {
//                iter.node.previous();
//            }
//        }
//        iter.node.add(secondPart);
//        size.getAndIncrement();
//    }
//
//    @Override
//    public synchronized int Remove(String val, int count) {
//        int removed = 0;
//        ListIterator<ArrayList<String>> listIterator = data.listIterator();
//        while (listIterator.hasNext()) {
//            ArrayList<String> page = listIterator.next();
//            if (page.contains(val)) {
//                page.remove(val);
//                size.getAndDecrement();
//                removed++;
//                if (removed == count) {
//                    break;
//                }
//            }
//        }
//        return removed;
////        QLIterator iterator = find(0);
////        if (iterator == null) {
////            return 0;
////        }
////
////        int removed = 0;
////        while (!iterator.atEnd()) {
////            String v = iterator.get();
////            if (v != null && v.equals(val)) {
////                iterator.remove();
////                removed++;
////                if (removed == count) {
////                    break;
////                }
////            } else {
////                iterator.next();
////            }
////        }
////        return removed;
//    }
//
//    public synchronized int reverseRemove(String val, int count) {
//        int removed = 0;
//        ListIterator<ArrayList<String>> listIterator = data.listIterator(data.size());
//        while (listIterator.hasPrevious()) {
//            ArrayList<String> page = listIterator.previous();
//            if (page.contains(val)) {
//                page.remove(val);
//                size.getAndDecrement();
//                removed++;
//                if (removed == count) {
//                    break;
//                }
//            }
//        }
//        return removed;
//    }
//
//    @Override
//    public synchronized int RemoveFrom(int direction, int count, String target) {
//        if (direction == FORWARD) {
//            return Remove(target, count);
//        }
//        return reverseRemove(target, count);
//    }
//
//    @Override
//    public synchronized String RemoveFirst() {
//        if (size.intValue() == 0) {
//            return null;
//        }
//        size.getAndDecrement();
//        ArrayList<String> firstPage = data.getFirst();
//        String val = firstPage.remove(0);
//        if (firstPage.size() == 0) {
//            data.removeFirst();
//        }
//        return val;
//    }
//
//    @Override
//    public synchronized String RemoveLast() {
//        if (size.intValue() == 0) {
//            return null;
//        }
//        size.getAndDecrement();
//        ArrayList<String> lastPage = data.getLast();
//        String val = lastPage.remove(lastPage.size()-1);
//        if (lastPage.size() == 0) {
//            data.removeLast();
//        }
//        return val;
//    }
//
//    @Override
//    public synchronized int Len() {
//        return size.intValue();
//    }
//
//    @Override
//    public synchronized void forEach(IListConsumer consumer) {
//        if (size.intValue() == 0) {
//            return;
//        }
//
//        int i = 0;
//        for (ArrayList<String> page : data) {
//            for (String item : page) {
//                if (!consumer.consumer(i, item)) {
//                    break;
//                }
//                i++;
//            }
//        }
////        QLIterator iterator = find(0);
////
////        if (iterator == null) {
////            return;
////        }
////
////        int i = 0;
////        while (true) {
////            if (!consumer.consumer(i, iterator.get())) {
////                break;
////            }
////            iterator.next();
////            i++;
////        }
//    }
//
//    @Override
//    public synchronized boolean contains(String obj) {
//        final boolean[] ret = {false};
//        forEach(new IListConsumer() {
//            @Override
//            public boolean consumer(int i, Object val) {
//                String s = (String) val;
//                if (s.equals(obj)) {
//                    ret[0] = true;
//                    return false;
//                }
//                return true;
//            }
//        });
//        return ret[0];
//    }
//
//    // [start, stop) 左闭右开
//    @Override
//    public synchronized String[] range(int start, int end) {
//        if (start < 0 || start >= size.intValue()) {
//            return null;
//        }
//        if (end < start || end > size.intValue()) {
//            return null;
//        }
//
//        int sliceSize = end - start;
//
//        QLIterator iterator = find(start);
//        if (iterator == null) {
//            return null;
//        }
//        String[] ret = new String[sliceSize];
//        for (int i=0;i<sliceSize;i++) {
//            ret[i] = iterator.get();
//            iterator.next();
//        }
//        return ret;
//    }
//
//    @Override
//    public synchronized int indexOfVal(String obj) {
//        final int[] index = {-1};
//        forEach(new IListConsumer() {
//            @Override
//            public boolean consumer(int i, Object val) {
//                String s = (String) val;
//                if (obj.equals(s)) {
//                    index[0] = i;
//                    return false;
//                }
//                return true;
//            }
//        });
//        return index[0];
//    }
//}
